package JzOffer.jz41;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * @author 张取
 * @version 1.0
 * @date 2022/1/7 下午10:27
 * JzOffer.jz41
 */

public class Solution02 {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入窗口大小:");
        int size = scanner.nextInt();
        MovingAverage02 obj = new MovingAverage02(size);
        int val;
        double res = 0;
        while(true){
            System.out.println("==================");
            val = scanner.nextInt();
            res = obj.next(val);
            System.out.println(res);
        }
    }
}

class MovingAverage02 {

    private Queue<Integer> queue;
    private final int size;
    /**
     * sum用于存储窗口中元素的和
     */
    private double sum;

    public MovingAverage02(int size){
        queue = new LinkedList<>();
        this.size = size;
    }

    /**
     * 采用sum来预先存储窗口中的元素的和，sum不依赖与队列，实现解耦；
     * 不遍历队列，时间复杂度为O(1).
     * */
    public double next(int val){
        if(queue.size() >= this.size && queue.peek() != null){
            //队头元素出队
            sum -= queue.poll();
        }
        queue.offer(val);
        sum += val;
        return sum / queue.size();
    }
}
